/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXI30/FONT#2=BAXB30/FONT#3=BAXS30/FONT#4=METLB/FONT#5=METMB/FONT#6=GACL25



␈↓ ↓N␈↓¬␈↓ ¬bNovember 1978




␈↓ ↓N␈↓¬␈↓ ε	Proposal to

␈↓ ↓N␈↓¬␈↓ ¬
␈↓∧University of California
␈↓ ↓N␈↓∧␈↓ ∧DLawrence Livermore Laboratory␈↓¬

␈↓ ↓N␈↓¬␈↓ ¬{for design of

␈↓ ↓N␈↓¬␈↓ βe␈↓∧An Operating System for the S-1 Computer␈↓¬


␈↓ ↓N␈↓¬␈↓ βvJohn McCarthy, Professor of Computer Science
␈↓ ↓N␈↓¬␈↓ β9Forest Baskett, Associate Professor of Computer Science
␈↓ ↓N␈↓¬␈↓ ¬∪Co-principal Investigators










␈↓ ↓N␈↓¬␈↓ ε≡Abstract


␈↓ ↓N␈↓¬The␈α
Stanford␈α
Artificial␈α
Intelligence␈α	Laboratory␈α
proposes␈α
to␈α
continue␈α
participation␈α	in
␈↓ ↓N␈↓¬the␈αLawrence␈αLivermore␈αLaboratory␈αprogram␈αfor␈αdevelopment␈αof␈αthe␈αS-1␈αcomputer
␈↓ ↓N␈↓¬system.  This proposal covers a one-year period beginning 1 January 1979.










␈↓ ↓N␈↓¬␈↓ ∧W␈↓∧Computer Science Department
␈↓ ↓N␈↓∧␈↓ ¬,Stanford University
␈↓ ↓N␈↓α␈↓ εS-1 Proposal␈↓ b1


␈↓ ↓N␈↓α␈↓ β(1.  Summary                                 ␈↓ π∞␈↓α␈↓ πQ2.  A Pascal Extension for Systems
                                            ␈↓ π∞␈↓ λ←␈↓αProgramming
␈↓ ↓N␈↓The␈α=Stanford␈α=Arti␈↓βC␈↓cial␈α=Intelligence
␈↓ ↓N␈↓Laboratory␈α∞proposes␈α∞to␈α∂continue␈α∞development     ␈↓ π∞␈↓An␈α
upward␈α
compatible␈α
extension␈α
of␈αthe␈α
Pascal
␈↓ ↓N␈↓work␈α∂on␈α∂the␈α∞S1␈α∂computer␈α∂system,␈α∂as␈α∞planned         ␈↓ π∞␈↓programming␈α∀language,␈α∪designed␈α∀to␈α∪support
␈↓ ↓N␈↓in␈α
our␈αproposal␈α
of␈αDecember␈α
1977␈α(Appendix        ␈↓ π∞␈↓the␈α∂development␈α∞of␈α∂large␈α∞system␈α∂programs,␈α∞is
␈↓ ↓N␈↓B).  This proposal covers calendar year 1979.␈↓ π∞␈↓described␈α≠in␈α≠the␈α≠attached␈α≠note␈α≤by␈α≠John
                                            ␈↓ π∞␈↓Hennessy␈α⊂and␈α⊂Forest␈α⊂Baskett,␈α⊂"An␈α∂Extension
␈↓ ↓N␈↓In␈α⊂the␈α∂period␈α⊂April␈α⊂1978␈α∂to␈α⊂the␈α⊂present,␈α∂the        ␈↓ π∞␈↓to␈α≠the␈α≠Programming␈α≠Language␈α≠Pascal␈α~to
␈↓ ↓N␈↓following has been accomplished.            ␈↓ π∞␈↓support Systems Programming".

␈↓ ↓N␈↓␈↓ α∞1.  Preliminary design of operating
␈↓ ↓N␈↓␈↓ α>system.

␈↓ ↓N␈↓␈↓ α∞2.  Support programs have been
␈↓ ↓N␈↓␈↓ α>developed as follows:
␈↓ ↓N␈↓␈↓ α>a.  S1 simulator,
␈↓ ↓N␈↓␈↓ α>b.  Cross-assembler for S1 code
␈↓ ↓N␈↓␈↓ αnrunning on PDP-10,
␈↓ ↓N␈↓␈↓ α>c.  S1 debugger,
␈↓ ↓N␈↓␈↓ α>d.  PDP-10 simulator for S1,
␈↓ ↓N␈↓␈↓ α>e.  AN UYK-7 simulator,
␈↓ ↓N␈↓␈↓ α>f.  Memory diagnostic

␈↓ ↓N␈↓␈↓ α∞3.  A set of numerical rountines has been
␈↓ ↓N␈↓␈↓ α>written for the S1 (SQRT, SIN, COS,
␈↓ ↓N␈↓␈↓ α>ATAN, LOG, EXP).

␈↓ ↓N␈↓␈↓ α∞4.  Detailed design and layout of the
␈↓ ↓N␈↓␈↓ α>memory switch is well underway.  At
␈↓ ↓N␈↓␈↓ α>this writing, all data paths and about
␈↓ ↓N␈↓␈↓ α>90% of the control logic have been
␈↓ ↓N␈↓␈↓ α>designed.  Diagnostic hardware
␈↓ ↓N␈↓␈↓ α>design is just beginning and physical
␈↓ ↓N␈↓␈↓ α>layout is yet to be done.

␈↓ ↓N␈↓␈↓ α∞5.  Assistance has been provided in other
␈↓ ↓N␈↓␈↓ α>hardware design, mainly the memory
␈↓ ↓N␈↓␈↓ α>interface for the Mark I processor.

␈↓ ↓N␈↓Professor␈α
Forest␈α
Baskett␈α
has␈α
joined␈α
the␈α
project
␈↓ ↓N␈↓as␈α*Co-principal␈α*Investigator␈α*and␈α)will
␈↓ ↓N␈↓coordinate␈α,system␈α-programming␈α,e␈↓β@␈↓orts.
␈↓ ↓N␈↓Professor␈α⊃John␈α⊃Hennessy␈α⊃has␈α⊃also␈α⊃joined␈α⊂in
␈↓ ↓N␈↓this␈αe␈↓β@␈↓ort.␈α
 See␈αAppendix␈αA␈α
for␈αmore␈αon␈α
their
␈↓ ↓N␈↓interests.
␈↓ ↓N␈↓α␈↓ εS-1 Proposal␈↓ `2


␈↓ ↓N␈↓α␈↓ β+Appendix A                                  ␈↓ π∞␈↓the␈α&construction␈α&of␈α&reliable␈α&distributed
␈↓ ↓N␈↓α␈↓ β≠New Personnel                               ␈↓ π∞␈↓software␈αsystems.␈α
 This␈αis␈α
important␈αto␈αthe␈α
S-1
                                            ␈↓ π∞␈↓project,␈α∪since␈α∪it␈α∪is␈α∪reasonable␈α∪to␈α∪consider␈α∩a
                                            ␈↓ π∞␈↓message␈α⊃passing␈α⊃system␈α⊃within␈α⊃the␈α⊂operating
␈↓ ↓N␈↓α␈↓ β∨Forest Baskett                              ␈↓ π∞␈↓system, as well as available to the users.

␈↓ ↓N␈↓Forest␈αBaskett␈αhas␈αbeen␈αinvolved␈αin␈αoperating
␈↓ ↓N␈↓system␈α∃design␈α∃and␈α∃development␈α∃since␈α∀1962.
␈↓ ↓N␈↓He␈α_worked␈α_with␈α_the␈α_Rice␈α→Computer␈α_and
␈↓ ↓N␈↓developed␈α≥parts␈α≤of␈α≥the␈α≥Codeword␈α≤based
␈↓ ↓N␈↓operating␈α⊗system␈α⊗for␈α∃that␈α⊗computer␈α⊗in␈α∃the
␈↓ ↓N␈↓early '60s.

␈↓ ↓N␈↓He␈α∩was␈α∪one␈α∩of␈α∪the␈α∩principal␈α∪designers␈α∩and
␈↓ ↓N␈↓implementers␈α⊂of␈α⊂one␈α⊂of␈α⊂the␈α⊂earliest␈α⊂and␈α⊂best
␈↓ ↓N␈↓time-sharing␈α
systems␈α∞on␈α
CDC␈α
6600's,␈α∞the␈α
UT
␈↓ ↓N␈↓operating␈α⊂system␈α⊂at␈α∂the␈α⊂University␈α⊂of␈α∂Texas.
␈↓ ↓N␈↓He␈α∞was␈α∞the␈α∞principal␈α∞designer␈α∞of␈α∞DEMOS,␈α∞a
␈↓ ↓N␈↓modern␈α!kernel␈α!based,␈α!process␈α!structured
␈↓ ↓N␈↓operating␈α∩system␈α∩for␈α∩the␈α∩CRAY-1.␈α∪ He␈α∩has
␈↓ ↓N␈↓published␈α~numerous␈α~papers␈α~on␈α→computing
␈↓ ↓N␈↓system design and development.

␈↓ ↓N␈↓α␈↓ β→John Hennessy 

␈↓ ↓N␈↓Professor␈α∪John␈α∪Hennessy's␈α∪research␈α∩interests
␈↓ ↓N␈↓include␈α_programming␈α↔language␈α_design␈α↔and
␈↓ ↓N␈↓implementation,␈α
operating␈α
systems␈α
design,␈αand
␈↓ ↓N␈↓distributed␈α*systems.␈α* In␈α*the␈α*area␈α*of
␈↓ ↓N␈↓programming␈α(language␈α(design␈α)he␈α(has
␈↓ ↓N␈↓designed␈α⊃a␈α⊃real-time␈α⊃programming␈α⊃language,
␈↓ ↓N␈↓providing␈α_support␈α↔for␈α_stand-alone␈α↔systems.
␈↓ ↓N␈↓Recently,␈α⊂under␈α⊂S-1␈α∂funding,␈α⊂he␈α⊂has␈α∂worked
␈↓ ↓N␈↓on␈α≡the␈α≡design␈α≡of␈α≡an␈α≡extension␈α≡of␈α≥the
␈↓ ↓N␈↓programming␈α≠language␈α≠Pascal,␈α≤to␈α≠support
␈↓ ↓N␈↓systems␈αprogramming␈αon␈α
the␈αS-1.␈α He␈αhas␈α
also
␈↓ ↓N␈↓been␈α
involved␈α
in␈α
the␈α
design␈α
and␈αmaintenance
␈↓ ↓N␈↓of␈α↔two␈α↔Pascal␈α↔compilers.␈α↔ Currently,␈α↔he␈α↔is
␈↓ ↓N␈↓initiating␈α⊃work␈α∩on␈α⊃the␈α⊃problems␈α∩of␈α⊃software
␈↓ ↓N␈↓portability␈αand␈αinteractive␈αhigh␈αlevel␈αlanguage
␈↓ ↓N␈↓debuggers.

␈↓ ↓N␈↓Professor␈α
Hennessy␈αis␈α
also␈αconducting␈α
research
␈↓ ↓N␈↓on␈α∞the␈α
topic␈α∞of␈α
distributed␈α∞computing␈α∞and␈α
its
␈↓ ↓N␈↓incorporation␈α∩into␈α∩a␈α∪programming␈α∩language.
␈↓ ↓N␈↓This␈αresearch␈αis␈αbased␈αon␈αthe␈αincorporation␈α
of
␈↓ ↓N␈↓message␈α5passing␈α5and␈α5synchronization
␈↓ ↓N␈↓capabilities␈α∂into␈α⊂a␈α∂standard␈α⊂process␈α∂structure.
␈↓ ↓N␈↓The␈αgoal␈αis␈αto␈αprovide␈αsimple␈αtools␈αto␈αsupport
␈↓ ↓N␈↓α␈↓ ε↑␈↓ `3


␈↓ ↓N␈↓α␈↓ β,Appendix B                                  ␈↓ π∞␈↓peripherals␈αwill␈α
connect␈αto␈αvarious␈α
S-1␈αsystem
␈↓ ↓N␈↓α␈↓ α$Text of December 1977 Proposal              ␈↓ π∞␈↓con␈↓βC␈↓gurations.

                                            ␈↓ π∞␈↓3)␈α
Support␈α
S-1␈α
Project␈α
hardware␈α
development,
                                            ␈↓ π∞␈↓in␈α∃fashions␈α∃and␈α∀to␈α∃extents␈α∃mutualy␈α∀agreed
                                            ␈↓ π∞␈↓upon␈α→by␈α→cognizant␈α→SAIL␈α→and␈α→LLL␈α_sta␈↓β@␈↓.
␈↓ ↓N␈↓α␈↓ βF1.  Goals                                   ␈↓ π∞␈↓During␈αthe␈αperiod␈α
of␈αthis␈αinitial␈αproposal␈α
such
                                            ␈↓ π∞␈↓support␈αactivity␈αwill␈αinclude␈αdetailed␈αdesign␈αof
␈↓ ↓N␈↓Building␈α~on␈α~a␈α~substantial␈α~background␈α~in          ␈↓ π∞␈↓the␈α#crossbar␈α$switch␈α#for␈α#the␈α$␈↓βC␈↓rst␈α#S-1
␈↓ ↓N␈↓computer␈αtimesharing␈αsystem␈αdevelopment␈α(see    ␈↓ π∞␈↓multiprocessor␈α→con␈↓βC␈↓guration␈α→and␈α→the␈α→post-
␈↓ ↓N␈↓Appendix␈α,B),␈α+the␈α,Stanford␈α+Arti␈↓βC␈↓cial             ␈↓ π∞␈↓construction␈α∞debugging␈α
and␈α∞documentation␈α
of
␈↓ ↓N␈↓Intelligence␈α_Laboratory␈α↔(SAIL)␈α_proposes␈α↔to      ␈↓ π∞␈↓this hardware module.
␈↓ ↓N␈↓participate␈α%in␈α%the␈α%Lawrence␈α$Livermore
␈↓ ↓N␈↓Laboratory␈α∪(LLL)␈α∪program␈α∪for␈α∩development
␈↓ ↓N␈↓of␈α_the␈α↔S-1␈α_computer␈α↔system␈α_by␈α↔designing
␈↓ ↓N␈↓certain␈α∩elements␈α∩and␈α∩developing␈α∪an␈α∩e␈↓β@␈↓icient      ␈↓ π∞␈↓α␈↓ λ`2.  Work Plan
␈↓ ↓N␈↓operating␈αsystem␈α
over␈αa␈α
period␈αof␈α
three␈αyears.
␈↓ ↓N␈↓This proposal covers the ␈↓βC␈↓rst 9 months' work.␈↓ π∞␈↓α␈↓ πM2.1  Operating System Development

␈↓ ↓N␈↓The␈α∩proposed␈α⊃work␈α∩will␈α⊃have␈α∩the␈α⊃following         ␈↓ π∞␈↓The␈α∀operating␈α∀system␈α∀to␈α∀be␈α∀developed␈α∀will
␈↓ ↓N␈↓subgoals:                                   ␈↓ π∞␈↓exploit␈α≡the␈α≡full␈α≡suite␈α≡of␈α∨capabilities␈α≡of
                                            ␈↓ π∞␈↓multiprocessor␈αS-1␈α
con␈↓βC␈↓gurations␈αand␈α
will␈αuse
␈↓ ↓N␈↓1)␈α~Design␈α~and␈α~begin␈α~development␈α~of␈α→an             ␈↓ π∞␈↓the␈α↔better␈α↔features␈α↔of␈α_existing␈α↔timesharing
␈↓ ↓N␈↓operating␈α'sysem␈α'for␈α'both␈α'single␈α&and              ␈↓ π∞␈↓systems,␈α↔such␈α↔as␈α↔Unix,␈α↔Multics,␈α↔TOPS-20,
␈↓ ↓N␈↓multiprocessor␈α~S-1␈α≠computer␈α~con␈↓βC␈↓gurations      ␈↓ π∞␈↓ITS,␈α∂and␈α∞the␈α∂Stanford␈α∞Monitor.␈α∂ However,␈α∞it
␈↓ ↓N␈↓with␈α
dedicated␈α
disk␈α
systems.␈α
 This␈α
system␈α
will    ␈↓ π∞␈↓will␈α⊂also␈α∂be␈α⊂capable␈α∂of␈α⊂specialization␈α⊂for␈α∂use
␈↓ ↓N␈↓provide␈α$e␈↓β@␈↓icient␈α#resource␈α$allocation␈α#for        ␈↓ π∞␈↓with␈α single␈α processor␈α!S-1␈α con␈↓βC␈↓gurations.
␈↓ ↓N␈↓con␈↓βC␈↓gurations␈α⊂of␈α⊂1␈α∂to␈α⊂32␈α⊂processors␈α⊂and␈α∂will       ␈↓ π∞␈↓There␈α≥will␈α≥also␈α≥be␈α≥some␈α≡innovation␈α≥in
␈↓ ↓N␈↓include␈α~user␈α~interactive␈α~facilities␈α~that␈α~are     ␈↓ π∞␈↓interactive user services.
␈↓ ↓N␈↓optimized␈α"for␈α"display␈α#terminals,␈α"though
␈↓ ↓N␈↓teleprinter␈α
terminals␈α
will␈α
also␈α
be␈αsupported.␈α
 In ␈↓ π∞␈↓A␈α~key␈α~problem␈α→to␈α~be␈α~solved␈α~is␈α→e␈↓β@␈↓icient
␈↓ ↓N␈↓addition␈αto␈αthe␈αoperating␈αsystem,␈αa␈α
number␈αof      ␈↓ π∞␈↓allocation␈α_and␈α_scheduling␈α_of␈α→resources.␈α_ It
␈↓ ↓N␈↓utility␈α⊂programs␈α⊂will␈α⊂be␈α⊂developed,␈α∂including    ␈↓ π∞␈↓should␈α$be␈α$possible␈α$to␈α$␈↓βD␈↓exibly␈α#allocate
␈↓ ↓N␈↓text␈α$editors,␈α$␈↓βC␈↓le␈α$management␈α#programs,          ␈↓ π∞␈↓processors␈α≡either␈α≡to␈α≥a␈α≡number␈α≡of␈α≥tasks
␈↓ ↓N␈↓compilers, and debuggers.                   ␈↓ π∞␈↓supporting␈α∩independent␈α∩users␈α∩or␈α∩to␈α∩separate
                                            ␈↓ π∞␈↓forks of a single task, depending on priorities.
␈↓ ↓N␈↓SAIL␈αrecognizes␈αthat␈αthe␈αS-1␈α
Project␈αrequires
␈↓ ↓N␈↓an␈α∂evolving␈α∞operating␈α∂system␈α∞for␈α∂the␈α∞various      ␈↓ π∞␈↓The␈α⊃planning␈α⊃phase␈α⊃of␈α⊃this␈α⊃work␈α∩(of␈α⊃about
␈↓ ↓N␈↓computer␈αcon␈↓βC␈↓gurations␈αit␈αis␈αcreating,␈αand␈αwill   ␈↓ π∞␈↓three␈αmonths'␈αduration)␈αwill␈αbe␈αdevoted␈αto␈αthe
␈↓ ↓N␈↓undertake␈α⊂to␈α⊂create␈α∂an␈α⊂operating␈α⊂system␈α∂that      ␈↓ π∞␈↓following tasks:
␈↓ ↓N␈↓will␈αhave␈αsome␈αminimal␈αcapability␈αearly␈αin␈αthe     ␈↓ π∞␈↓␈↓ π≡(1) familiarization with the S-1 equipment
␈↓ ↓N␈↓e␈↓β@␈↓ort,␈α~growing␈α~thereafter␈α~in␈α~capability␈α→in       ␈↓ π∞␈↓␈↓ πNcharacteristics;
␈↓ ↓N␈↓frequent increments.                        ␈↓ π∞␈↓␈↓ π≡(2) characterization of the principal kinds of
                                            ␈↓ π∞␈↓␈↓ πNcomputing tasks that are to be performed
␈↓ ↓N␈↓2)␈α Based␈αon␈αwork␈αdone␈αin␈αpursuit␈αof␈αthe␈α␈↓βC␈↓rst        ␈↓ π∞␈↓␈↓ πNwith this system;
␈↓ ↓N␈↓subgoal,␈α,recommend␈α,speci␈↓βC␈↓c␈α,equipment           ␈↓ π∞␈↓␈↓ π≡(3) general design of program services to be
␈↓ ↓N␈↓characteristics␈α≥needed␈α≥to␈α≡support␈α≥e␈↓β@␈↓icient      ␈↓ π∞␈↓␈↓ πNprovided by the operating system,
␈↓ ↓N␈↓operation.␈α≥ This␈α≥particularly␈α≡includes␈α≥the      ␈↓ π∞␈↓␈↓ πNincluding primary memory allocation and
␈↓ ↓N␈↓manner␈α⊗in␈α⊗which␈α⊗secondary␈α⊗memories␈α⊗and           ␈↓ π∞␈↓␈↓ πN␈↓βC␈↓le system characteristics;
␈↓ ↓N␈↓αWork Plan␈↓ ∧m2.1  Operating System Development␈↓ ]4


␈↓ ↓N␈↓␈↓ ↓↑(4) general design of user services, including␈↓ π∞␈↓SAIL␈α≤proposes␈α≠to␈α≤perform␈α≤the␈α≠following
␈↓ ↓N␈↓␈↓ α∞display control, command languages, and     ␈↓ π∞␈↓subtasks␈α
of␈α∞this␈α
basic␈α∞task␈α
during␈α∞the␈α
current
␈↓ ↓N␈↓␈↓ α∞character set standards;                    ␈↓ π∞␈↓proposal period:
␈↓ ↓N␈↓␈↓ ↓↑(5) analysis of other resource allocation issues;␈↓ π∞␈↓␈↓ π≡1) Familiarization of SAIL design personnel
␈↓ ↓N␈↓␈↓ ↓↑(6) study of major existing operating systems␈↓ π∞␈↓␈↓ πNwith the S-1 Design System.
␈↓ ↓N␈↓␈↓ α∞to determine which of their features may    ␈↓ π∞␈↓␈↓ π≡2) Complete logical design of the switch
␈↓ ↓N␈↓␈↓ α∞be pro␈↓βC␈↓tably included in the one to be      ␈↓ π∞␈↓␈↓ πNusing the S-1 Design System Graphics
␈↓ ↓N␈↓␈↓ α∞created, and which, if any, of their major  ␈↓ π∞␈↓␈↓ πNLanguage.
␈↓ ↓N␈↓␈↓ α∞modules may be appropriately carried        ␈↓ π∞␈↓␈↓ π≡3) Complete physical design of the switch,
␈↓ ↓N␈↓␈↓ α∞over into the new operating system;         ␈↓ π∞␈↓␈↓ πNincluding layout and cable assignment.
␈↓ ↓N␈↓␈↓ ↓↑(7) formulation of criteria for selection of␈↓ π∞␈↓␈↓ π≡4) Production of ␈↓βC␈↓nal wire-lists through the
␈↓ ↓N␈↓␈↓ α∞programming languages to be used in         ␈↓ π∞␈↓␈↓ πNS-1 Design System.
␈↓ ↓N␈↓␈↓ α∞major development tasks.                    ␈↓ π∞␈↓␈↓ π≡5) Debugging, including demonstration of
␈↓ ↓N␈↓This␈α⊃phase␈α⊂of␈α⊃the␈α⊂work␈α⊃will␈α⊃culminate␈α⊂with         ␈↓ π∞␈↓␈↓ πNfull switch functionality, using the LLL-
␈↓ ↓N␈↓the␈α∩generation␈α∩of␈α∩a␈α∩report␈α∪documenting␈α∩the        ␈↓ π∞␈↓␈↓ πNsupplied LSI-11 diagnostic system.
␈↓ ↓N␈↓results of performing these 7 tasks.        ␈↓ π∞␈↓␈↓ π≡6) Documentation, including a structured text
                                            ␈↓ π∞␈↓␈↓ πNdescription of the hardware to augment
␈↓ ↓N␈↓Other␈α∂products␈α∞of␈α∂this␈α∞phase␈α∂will␈α∂include␈α∞an       ␈↓ π∞␈↓␈↓ πNthe structured drawings, and a high-level
␈↓ ↓N␈↓assortment␈αof␈αplanning␈αdocuments␈αand␈αspeci␈↓βC␈↓c     ␈↓ π∞␈↓␈↓ πNdescription of switch operation.
␈↓ ↓N␈↓recommendations␈α∞on␈α∞equipment␈α∂design␈α∞issues,
␈↓ ↓N␈↓such␈α∞as␈α
how␈α∞the␈α
disk␈α∞storage␈α
units␈α∞should␈α
be        ␈↓ π∞␈↓All␈α≥aspects␈α≥of␈α≥crossbar␈α≡switch␈α≥hardware
␈↓ ↓N␈↓interfaced to the multiprocessor system.    ␈↓ π∞␈↓implementation␈α$is␈α#proposed␈α$to␈α$be␈α#the
                                            ␈↓ π∞␈↓responsibility␈α⊂of␈α⊂LLL.␈α⊂ At␈α⊂the␈α⊃completion␈α⊂of
␈↓ ↓N␈↓The␈α∪subsequent␈α∩design␈α∪phase␈α∩(of␈α∪about␈α∩six         ␈↓ π∞␈↓Step␈α⊂4␈α∂(above),␈α⊂it␈α∂is␈α⊂proposed␈α∂that␈α⊂LLL␈α∂will
␈↓ ↓N␈↓months'␈α
duration)␈α
will␈α
focus␈α
on␈αdetailed␈α
design   ␈↓ π∞␈↓construct␈α∞the␈α
switch,␈α∞associated␈α∞cabinetry,␈α
and
␈↓ ↓N␈↓of␈α→the␈α→functional␈α→elements␈α→of␈α→the␈α→system,         ␈↓ π∞␈↓LSI-11␈α⊃debug␈α∩processor,␈α⊃and␈α∩will␈α⊃thereupon
␈↓ ↓N␈↓selection␈α⊗of␈α∃system␈α⊗programming␈α∃languages,      ␈↓ π∞␈↓make␈α⊃the␈α⊂switch␈α⊃available␈α⊂for␈α⊃debugging␈α⊂by
␈↓ ↓N␈↓programming␈α≠of␈α≠developmental␈α≠tools␈α≠(e.g.,       ␈↓ π∞␈↓SAIL␈αsta␈↓β@␈↓.␈α Throughout␈αthe␈αdesign,␈αcognizant
␈↓ ↓N␈↓simple␈α∪editors␈α∪and␈α∪debuggers),␈α∪and␈α∪possibly      ␈↓ π∞␈↓SAIL␈α
sta␈↓β@␈↓␈α
members␈α
will␈α
maintain␈α
close␈α
contact
␈↓ ↓N␈↓the␈αmodi␈↓βC␈↓cation␈α
of␈αa␈α
compiler␈αto␈α
produce␈αS-1       ␈↓ π∞␈↓with cognizant LLL sta␈↓β@␈↓ members.
␈↓ ↓N␈↓code.

␈↓ ↓N␈↓α␈↓ αB2.2  Crossbar Switch Design
                                            ␈↓ π∞␈↓α␈↓ λl3.  Facilities
␈↓ ↓N␈↓It␈α∂is␈α∂proposed␈α∂to␈α∂design␈α∂a␈α∂crossbar␈α⊂switch␈α∂to
␈↓ ↓N␈↓connect␈α∀16␈α∀S-1␈α∀processors␈α∀with␈α∀16␈α∪memory          ␈↓ π∞␈↓Much␈α≡of␈α∨the␈α≡planning␈α∨and␈α≡preliminary
␈↓ ↓N␈↓modules␈α∞with␈α∂a␈α∞maximum␈α∞concurrency␈α∂of␈α∞16,         ␈↓ π∞␈↓programming␈α⊃work␈α⊃on␈α⊃both␈α⊃projects␈α⊃will␈α⊃be
␈↓ ↓N␈↓and␈α↔a␈α↔throughput␈α↔of␈α↔70␈α_nanoseconds␈α↔per            ␈↓ π∞␈↓performed␈α∂on␈α⊂the␈α∂existing␈α⊂computer␈α∂facilities
␈↓ ↓N␈↓word,␈αas␈α
speci␈↓βC␈↓ed␈αin␈α
Reference␈α1.␈α
 The␈αswitch      ␈↓ π∞␈↓of␈α+the␈α+Stanford␈α+Arti␈↓βC␈↓cial␈α*Intelligence
␈↓ ↓N␈↓will␈α
contain␈α
logic␈α
to␈α
allow␈α
an␈α
LSI-11␈α
processor,   ␈↓ π∞␈↓Laboratory.␈α Since␈αthis␈αequipment␈αhas␈αalready
␈↓ ↓N␈↓connected␈α⊃through␈α⊃an␈α⊃LLL-supplied␈α⊃parallel      ␈↓ π∞␈↓been␈α,purchased,␈α,mostly␈α,with␈α,U.␈α+S.
␈↓ ↓N␈↓interface,␈α
to␈αperform␈α
comprehensive␈α
testing␈αof   ␈↓ π∞␈↓Government␈α⊗research␈α⊗funds,␈α⊗the␈α⊗only␈α⊗costs
␈↓ ↓N␈↓the␈αswitch␈α(both␈αby␈αproviding␈αarti␈↓βC␈↓cial␈αstimuli   ␈↓ π∞␈↓involved␈αin␈αits␈αuse␈αwill␈αbe␈αthe␈αsupport␈αof␈αpart
␈↓ ↓N␈↓to␈α∀the␈α∪switch,␈α∀and␈α∀by␈α∪reading␈α∀the␈α∀state␈α∪of          ␈↓ π∞␈↓of␈αa␈αcomputer␈αtechnician␈αand␈αa␈αshare␈αof␈αother
␈↓ ↓N␈↓switch␈αbuses␈αand␈α
signals)␈αand␈αto␈α
recover␈αfrom      ␈↓ π∞␈↓maintenance costs.
␈↓ ↓N␈↓what␈α(are␈α(considered␈α(to␈α)be␈α(probable
␈↓ ↓N␈↓recoverable␈α≥failure␈α≥modes␈α≥of␈α≥the␈α≤switch,         ␈↓ π∞␈↓It␈αis␈αproposed␈αthat␈αLLL␈αmake␈αavailable␈αto␈αthe
␈↓ ↓N␈↓processors, and memory modules.             ␈↓ π∞␈↓Stanford␈α∨Arti␈↓βC␈↓cial␈α∨Intelligence␈α∨Laboratory
                                            ␈↓ π∞␈↓fractions␈α⊗of␈α∃the␈α⊗capabilities␈α∃of␈α⊗both␈α∃single
␈↓ ↓N␈↓αFacilities␈↓ ε↑␈↓ ←5


␈↓ ↓N␈↓processor␈α?␈απand␈α?␈απmultiprocessor␈α?␈απS-1               ␈↓ π∞␈↓and␈α
will␈α
include␈α∞the␈α
description␈α
of␈α∞the␈α
switch
␈↓ ↓N␈↓con␈↓βC␈↓gurations␈α∩appropriate␈α∩to␈α∪various␈α∩phases     ␈↓ π∞␈↓design␈αimplementation␈α
and␈αdebugging␈αwork␈α
of
␈↓ ↓N␈↓of␈α∀advanced␈α∀operating␈α∃systems␈α∀development       ␈↓ π∞␈↓Section␈α2.2.␈α All␈αthese␈αreports␈αwill␈αbe␈α
delivered
␈↓ ↓N␈↓and␈α
debugging.␈α
 Determination␈αof␈α
how␈α
this␈αis      ␈↓ π∞␈↓to␈α∪LLL␈α∀within␈α∪30␈α∀days␈α∪of␈α∀the␈α∪end␈α∀of␈α∪the
␈↓ ↓N␈↓to␈α∩be␈α∩most␈α⊃e␈↓β@␈↓ectively␈α∩accomplished␈α∩is␈α∩to␈α⊃be        ␈↓ π∞␈↓periods on whose results they report.
␈↓ ↓N␈↓made␈α∀jointly␈α∃by␈α∀cognizant␈α∀LLL␈α∃and␈α∀SAIL
␈↓ ↓N␈↓personnel,␈α∨as␈α∨such␈α∨needs␈α∨evolve.␈α∨ It␈α≡is
␈↓ ↓N␈↓anticipated␈α∃that␈α∃some␈α∃phone␈α∃line␈α⊗access␈α∃to
␈↓ ↓N␈↓LLL-based␈α⊃S-1␈α⊃hardware␈α⊃con␈↓βC␈↓gurations␈α⊂will
␈↓ ↓N␈↓be␈α
needed␈αand␈α
a␈α
budget␈αitem␈α
to␈α
support␈αsuch
␈↓ ↓N␈↓access is included.



␈↓ ↓N␈↓α␈↓ α)4.  Coordination and Reporting

␈↓ ↓N␈↓It␈α≠is␈α≠proposed␈α≠that␈α≠primary␈α≠coordination
␈↓ ↓N␈↓between␈α≡cognizant␈α≡LLL␈α≡and␈α≡SAIL␈α≥sta␈↓β@␈↓
␈↓ ↓N␈↓members␈α'be␈α'accompished␈α'via␈α&monthly
␈↓ ↓N␈↓meetings,␈α⊃to␈α⊃be␈α⊃conducted␈α⊃for␈α⊃approximately
␈↓ ↓N␈↓half-day␈α#periods.␈α# Senior␈α#SAIL␈α"Project
␈↓ ↓N␈↓members␈α~will␈α~document␈α~the␈α~salient␈α→topics
␈↓ ↓N␈↓addressed␈α≡at␈α≥these␈α≡conferences␈α≥(including
␈↓ ↓N␈↓accomplishments␈α⊂of␈α∂the␈α⊂previous␈α⊂month,␈α∂and
␈↓ ↓N␈↓the␈α→relatively␈α→detailed␈α→work␈α→plan␈α→for␈α→the
␈↓ ↓N␈↓upcoming␈α(month)␈α(and␈α(distribute␈α(such
␈↓ ↓N␈↓documents␈α∪to␈α∪all␈α∪cognizant␈α∪SAIL␈α∀and␈α∪LLL
␈↓ ↓N␈↓sta␈↓β@␈↓␈α%members␈α$as␈α%the␈α%primary␈α$project
␈↓ ↓N␈↓coordination papers.

␈↓ ↓N␈↓SAIL␈αproposes␈α
to␈αsubmit␈α
two␈αinterim␈α
technical
␈↓ ↓N␈↓reports␈α↔to␈α↔LLL␈α↔dealing␈α↔with␈α↔the␈α↔progress
␈↓ ↓N␈↓made␈αduring␈αthe␈αWinter␈αand␈αSpring␈αQuarters
␈↓ ↓N␈↓of␈α∀1978,␈α∃and␈α∀a␈α∀␈↓βC␈↓nal,␈α∃comprehensive␈α∀report
␈↓ ↓N␈↓which␈α∞treats␈α∂in␈α∞detail␈α∞all␈α∂aspects␈α∞of␈α∂the␈α∞work
␈↓ ↓N␈↓done␈α↔during␈α↔the␈α_January-September,␈α↔1978,
␈↓ ↓N␈↓period.␈α_ It␈α_is␈α_anticipated␈α_that␈α→the␈α_Winter
␈↓ ↓N␈↓Quarter␈α
document␈α
will␈α
report␈α
the␈α
results␈α
of␈α
the
␈↓ ↓N␈↓7-point␈α operating␈α sysem␈α planning␈α phase
␈↓ ↓N␈↓discussed␈α∩in␈α⊃Section␈α∩2.1,␈α∩as␈α⊃well␈α∩as␈α∩the␈α⊃␈↓βC␈↓rst
␈↓ ↓N␈↓three␈αitems␈α
of␈αthe␈α
crossbar␈αswitch␈α
development
␈↓ ↓N␈↓discussed␈α≡in␈α≡Section␈α≡2.2.␈α≡ It␈α≡is␈α≡likewise
␈↓ ↓N␈↓expected␈α∩that␈α∪the␈α∩Spring␈α∪Quarter␈α∩document
␈↓ ↓N␈↓will␈αreport␈αpreliminary␈αresults␈αof␈αthe␈α
operating
␈↓ ↓N␈↓system␈α⊂design␈α⊃phase␈α⊂of␈α⊃Section␈α⊂2.1,␈α⊃and␈α⊂will
␈↓ ↓N␈↓also␈α∞report␈α∞successful␈α∞completion␈α∞of␈α∞at␈α∞least␈α∞2
␈↓ ↓N␈↓of␈αthe␈α␈↓βC␈↓nal␈α3␈αitems␈αof␈αthe␈α
switch␈αdevelopment
␈↓ ↓N␈↓of␈αSection␈α2.2.␈α The␈α␈↓βC␈↓nal␈αreport␈αwill␈αdetail␈αthe
␈↓ ↓N␈↓design␈α∞of␈α∞the␈α
operating␈α∞system␈α∞of␈α∞Section␈α
2.1,
␈↓ ↓N␈↓α␈↓ ε↑␈↓ `6


␈↓ ↓N␈↓α␈↓ β+Appendix C                                  ␈↓ π∞␈↓realtime␈α≠control␈α≤of␈α≠mechanical␈α≤arms␈α≠and
␈↓ ↓N␈↓α␈↓ ↓`SAIL Background in System Development       ␈↓ π∞␈↓television␈α⊂cameras,␈α⊂in␈α⊂support␈α⊂of␈α⊃research␈α⊂in
                                            ␈↓ π∞␈↓automatic␈α∂mechanical␈α∂assembly␈α∂and␈α∞computer
                                            ␈↓ π∞␈↓vision [7].
␈↓ ↓N␈↓While␈α⊃the␈α⊃primary␈α⊃interests␈α⊃of␈α∩the␈α⊃Stanford
␈↓ ↓N␈↓Arti␈↓βC␈↓cial␈αIntelligence␈αLaboratory␈αhave␈αbeen␈αin   ␈↓ π∞␈↓In␈α∩the␈α∩period␈α∩1970-73,␈α∩SAIL␈α∩sta␈↓β@␈↓␈α∩members
␈↓ ↓N␈↓arti␈↓βC␈↓cial␈α∪intelligence,␈α∪mathematical␈α∀theory␈α∪of  ␈↓ π∞␈↓designed␈α∀a␈α∀high␈α∀speed␈α∀processor␈α∀known␈α∀as
␈↓ ↓N␈↓computation,␈α
and␈α
related␈α
theoretical␈αproblems,  ␈↓ π∞␈↓"Super␈α≥Foonly",␈α≡which␈α≥featured␈α≡a␈α≥cache
␈↓ ↓N␈↓certain␈α
members␈α
of␈α∞the␈α
SAIL␈α
sta␈↓β@␈↓␈α∞have␈α
been         ␈↓ π∞␈↓memory,␈α≤user-accessible␈α≤microcode,␈α≥and␈α≤a
␈↓ ↓N␈↓involved␈α⊂for␈α∂many␈α⊂years␈α∂in␈α⊂the␈α∂development        ␈↓ π∞␈↓"console␈α∨computer"␈α∨(a␈α∨minicomputer␈α≡that
␈↓ ↓N␈↓of␈α4timesharing␈α4systems,␈α4programming            ␈↓ π∞␈↓monitors␈α~the␈α→main␈α~processor).␈α~ The␈α→latter
␈↓ ↓N␈↓languages,␈α∂and␈α∂interactive␈α∂facilities.␈α∂ Some␈α∂of  ␈↓ π∞␈↓innovation␈α→has␈α→since␈α→been␈α→included␈α~in␈α→a
␈↓ ↓N␈↓these activities are outlined below.        ␈↓ π∞␈↓number␈α
of␈α
other␈α
machines,␈α
including␈α
the␈αS-1.
                                            ␈↓ π∞␈↓After␈α∂the␈α∞design␈α∂was␈α∞completed,␈α∂it␈α∂was␈α∞made
␈↓ ↓N␈↓The␈αconcept␈αof␈αa␈αgeneral␈αpurpose␈αtimesharing      ␈↓ π∞␈↓available␈α∩to␈α∩Digital␈α∩Equipment␈α∩Corporation,
␈↓ ↓N␈↓system␈α∂was␈α∂␈↓βC␈↓rst␈α∞proposed␈α∂by␈α∂John␈α∞McCarthy         ␈↓ π∞␈↓which␈α used␈α it␈α!as␈α the␈α basis␈α!for␈α their
␈↓ ↓N␈↓when␈α∞he␈α∞was␈α∞at␈α
MIT␈α∞[2].␈α∞ That␈α∞proposal␈α
led          ␈↓ π∞␈↓Decsystem/10␈α!and␈α"Decsystem/20␈α!computer
␈↓ ↓N␈↓to␈αthe␈αpioneering␈αsystems␈αdeveloped␈αin␈αProject    ␈↓ π∞␈↓systems.␈α⊃ The␈α⊃KL10␈α⊃processor␈α⊃now␈α∩at␈α⊃SAIL
␈↓ ↓N␈↓MAC.␈α↔ McCarthy␈α_also␈α↔participated␈α_in␈α↔the          ␈↓ π∞␈↓was␈α
donated␈αby␈α
DEC␈α
out␈αof␈α
gratitude␈α
for␈αthe
␈↓ ↓N␈↓development␈αof␈αan␈αearly␈αtimesharing␈αsystem␈αat     ␈↓ π∞␈↓design contribution.
␈↓ ↓N␈↓BBN [3].
                                            ␈↓ π∞␈↓Another␈α
important␈α
outgrowth␈α
of␈α
this␈α
computer
␈↓ ↓N␈↓Shortly␈α∀after␈α∀arriving␈α∀at␈α∀Stanford␈α∀in␈α∀1962,       ␈↓ π∞␈↓design␈αproject␈αwas␈αa␈αdesign␈αautomation␈αsystem
␈↓ ↓N␈↓McCarthy␈α∂undertook␈α⊂the␈α∂development␈α⊂of␈α∂the        ␈↓ π∞␈↓known␈α"as␈α#SUDS␈α"[8],␈α#which␈α"combined
␈↓ ↓N␈↓␈↓βC␈↓rst␈α∪display-oriented␈α∪timesharing␈α∪system␈α∪[4],   ␈↓ π∞␈↓interactive␈α"drawing␈α"facilities␈α#with␈α"other
␈↓ ↓N␈↓based␈α
on␈αa␈α
PDP-1␈αcomputer␈α
with␈α
12␈αdisplays         ␈↓ π∞␈↓computer-aided␈αdesign␈αservices.␈α This␈αwas␈αthe
␈↓ ↓N␈↓and␈α∪a␈α∪link␈α∪to␈α∩an␈α∪IBM␈α∪7090.␈α∪ One␈α∩notable             ␈↓ π∞␈↓␈↓βC␈↓rst␈αsystem␈αthat␈αpermitted␈αa␈αdesigner,␈αworking
␈↓ ↓N␈↓accomplishment␈α∨of␈α∨this␈α∨project␈α∨was␈α∨the           ␈↓ π∞␈↓through␈α~a␈α→display␈α~terminal,␈α~to␈α→completely
␈↓ ↓N␈↓development␈α#of␈α#a␈α#"page␈α#editor"␈α"called            ␈↓ π∞␈↓design␈α≡complex␈α≡digital␈α≡devices,␈α≥including
␈↓ ↓N␈↓TVEDIT␈α∃that␈α∃exploited␈α∃the␈α∃capabilities␈α∀of        ␈↓ π∞␈↓printed␈α⊂circuit␈α⊂boards␈α⊂and␈α⊂backpanel␈α∂wiring.
␈↓ ↓N␈↓displays␈α≡in␈α≡text␈α≡editing.␈α≡ This␈α≡was␈α≥the           ␈↓ π∞␈↓The␈α
system␈α
automatically␈α
produces␈α
artwork␈α
for
␈↓ ↓N␈↓forerunner␈α∪of␈α∪screen␈α∀editors␈α∪now␈α∪in␈α∀use␈α∪at         ␈↓ π∞␈↓PC␈α∪boards␈α∪and␈α∪control␈α∪tapes␈α∪for␈α∪automatic
␈↓ ↓N␈↓SAIL␈α∪and␈α∩in␈α∪a␈α∩number␈α∪of␈α∪other␈α∩advanced             ␈↓ π∞␈↓wiring␈α∃machines.␈α∀ SUDS␈α∃has␈α∀been␈α∃used␈α∀to
␈↓ ↓N␈↓timesharing systems.                        ␈↓ π∞␈↓design␈α∂␈↓βC␈↓ve␈α∞large␈α∂computers␈α∞so␈α∂far,␈α∞as␈α∂well␈α∞as
                                            ␈↓ π∞␈↓countless␈α∞other␈α∞digital␈α∞devices.␈α∞ It␈α∞is␈α∞currently
␈↓ ↓N␈↓When␈α!the␈α!SAIL␈α!computer␈α!facility␈α was              ␈↓ π∞␈↓in␈α⊃use␈α∩at␈α⊃MIT,␈α∩Carnegie-Mellon␈α⊃University,
␈↓ ↓N␈↓assembled␈α∪in␈α∀1966,␈α∪the␈α∀sta␈↓β@␈↓␈α∪of␈α∀the␈α∪PDP-1           ␈↓ π∞␈↓and␈α∀Digital␈α∪Equipment␈α∀Corporation,␈α∪among
␈↓ ↓N␈↓timesharing␈αproject␈αbecame␈αthe␈αnucleus␈αof␈αthe     ␈↓ π∞␈↓other␈α⊗places,␈α⊗and␈α⊗is␈α⊗the␈α⊗basis␈α⊗of␈α⊗the␈α∃S-1
␈↓ ↓N␈↓computer␈α system␈α∨sta␈↓β@␈↓␈α that␈α developed␈α∨a            ␈↓ π∞␈↓Design System.
␈↓ ↓N␈↓display-oriented␈α⊗system␈α↔on␈α⊗a␈α↔DEC␈α⊗PDP-6
␈↓ ↓N␈↓computer␈α∃initially␈α∃and␈α∃later␈α∃on␈α∃KA10␈α∀and          ␈↓ π∞␈↓Other␈α∂interests␈α∞of␈α∂the␈α∞SAIL␈α∂sta␈↓β@␈↓␈α∂include␈α∞the
␈↓ ↓N␈↓KL10␈α→processors.␈α→ There␈α→are␈α→currently␈α→70         ␈↓ π∞␈↓development␈α≠of␈α≠assemblers␈α≠[9],␈α≠the␈α≠LISP
␈↓ ↓N␈↓display␈αterminals␈α
connected␈αto␈α
the␈αsystem,␈α
most   ␈↓ π∞␈↓family␈αof␈αprogramming␈αlanguages␈αand␈αsystems
␈↓ ↓N␈↓of␈α⊃them␈α⊃with␈α∩full␈α⊃graphics␈α⊃capability␈α∩[5,␈α⊃6].      ␈↓ π∞␈↓[10,␈α
11,␈α∞12],␈α
the␈α∞SAIL␈α
language␈α∞and␈α
compiler
␈↓ ↓N␈↓There␈α∪is␈α∪also␈α∪a␈α∪connection␈α∪to␈α∪the␈α∩Arpanet,         ␈↓ π∞␈↓[13],␈α
text␈α
editors␈α
[14,␈α
15],␈αinteractive␈α
debuggers
␈↓ ↓N␈↓permitting␈α$remote␈α$access␈α$to␈α$and␈α#from             ␈↓ π∞␈↓[16],␈α⊃document␈α⊂compilers␈α⊃[17],␈α⊃and␈α⊂computer
␈↓ ↓N␈↓hundreds␈α~of␈α~other␈α~computers␈α~around␈α~the           ␈↓ π∞␈↓communication systems [18].
␈↓ ↓N␈↓world.␈α
 In␈α∞addition␈α
to␈α∞providing␈α
conventional
␈↓ ↓N␈↓timesharing␈α∨services,␈α∨this␈α∨system␈α∨handles       ␈↓ π∞␈↓The␈α
backgrounds␈α
of␈α
the␈α
individuals␈α
who␈α
will
␈↓ ↓N␈↓αAppendix C␈↓ ∧@SAIL Background in System Development␈↓ `7


␈↓ ↓N␈↓carry␈α⊃out␈α⊃the␈α⊃proposed␈α⊃work␈α⊃are␈α∩as␈α⊃follows.        ␈↓ π∞␈↓[5]    Brian Harvey and Martin Frost,
␈↓ ↓N␈↓John␈α_McCarthy,␈α↔who␈α_will␈α_provide␈α↔overall          ␈↓ π∞␈↓␈↓ π>␈↓αMonitor Command Manual␈↓, SAILON-
␈↓ ↓N␈↓direction␈α⊗of␈α⊗the␈α⊗project,␈α⊗is␈α⊗a␈α⊗Professor␈α∃of        ␈↓ π∞␈↓␈↓ π>54.5, January 1976.
␈↓ ↓N␈↓Computer␈α
Science␈α∞and␈α
Director␈α
of␈α∞SAIL.␈α
 He
␈↓ ↓N␈↓has␈α∂26␈α∂years␈α∞experience␈α∂as␈α∂a␈α∂faculty␈α∞member        ␈↓ π∞␈↓[6]    McCarthy, John, Lester Earnest, D. Raj.
␈↓ ↓N␈↓at␈α∩a␈α∩number␈α∩of␈α∩major␈α∩universities␈α∩and␈α∩has          ␈↓ π∞␈↓␈↓ π>Reddy, Pierre Vicens, ␈↓αA Computer with
␈↓ ↓N␈↓been␈α a␈α principal␈α innovator␈α!in␈α arti␈↓βC␈↓cial          ␈↓ π∞␈↓α␈↓ π>Hands, Eyes, and Ears␈↓, ␈↓↓Proc. AFIPS Conf.␈↓
␈↓ ↓N␈↓intelligence,␈α<mathematical␈α=theory␈α<of           ␈↓ π∞␈↓␈↓ π>(FJCC), 1968.
␈↓ ↓N␈↓computation,␈α⊗and␈α⊗timesharing␈α↔systems.␈α⊗ Les
␈↓ ↓N␈↓Earnest,␈α⊃who␈α⊃is␈α⊃Associate␈α⊃Director␈α∩of␈α⊃SAIL,       ␈↓ π∞␈↓[7]    Martin Frost, ␈↓αUUO Manual␈↓, SAILON-
␈↓ ↓N␈↓will␈α⊂handle␈α∂much␈α⊂of␈α∂the␈α⊂management␈α⊂of␈α∂the          ␈↓ π∞␈↓␈↓ π>55.5, October 1977.
␈↓ ↓N␈↓project.␈α≠ He␈α≤has␈α≠24␈α≠years␈α≤experience␈α≠in
␈↓ ↓N␈↓programming,␈α_computer␈α_system␈α_design␈α↔and         ␈↓ π∞␈↓[8]    Richard Helliwell, ␈↓αStanford Drawing
␈↓ ↓N␈↓technical management.                       ␈↓ π∞␈↓α␈↓ π>Program␈↓, SAIL Program Note, 1971.

␈↓ ↓N␈↓Je␈↓β@␈↓␈α→Rubin,␈α→who␈α→will␈α→head␈α→the␈α_operating            ␈↓ π∞␈↓[9]    Fred Wright and Ralph Gorin, ␈↓αFAIL␈↓,
␈↓ ↓N␈↓system␈α∞design␈α∞e␈↓β@␈↓ort,␈α∂is␈α∞currently␈α∞in␈α∂charge␈α∞of     ␈↓ π∞␈↓␈↓ π>Stanford AI Memo AIM-226, April 1974.
␈↓ ↓N␈↓system␈α∞programming␈α
at␈α∞SAIL␈α
and␈α∞has␈α
twelve
␈↓ ↓N␈↓years␈α⊂experience␈α⊂as␈α⊂a␈α⊂programmer,␈α⊂including      ␈↓ π∞␈↓[10]    John McCarthy, ␈↓αRecursive Functions
␈↓ ↓N␈↓six␈αyears␈αas␈αa␈αsystem␈αprogrammer␈αat␈αMIT␈αand         ␈↓ π∞␈↓α␈↓ π>of Symbolic Expressions␈↓, ␈↓↓Communications
␈↓ ↓N␈↓four␈α∃years␈α∃in␈α∃this␈α∃capacity␈α∃at␈α∃SAIL.␈α∃ Ted          ␈↓ π∞␈↓↓␈↓ π>of the ACM␈↓, April 1960.
␈↓ ↓N␈↓Panofsky,␈αwho␈αwill␈αdesign␈αthe␈αcrossbar␈αswitch,
␈↓ ↓N␈↓is␈αhead␈αof␈αthe␈αSAIL␈αComputer␈αFacility␈αgroup,       ␈↓ π∞␈↓[11]    John McCarthy, ␈↓↓et al, LISP 1.5
␈↓ ↓N␈↓has␈α⊂been␈α∂a␈α⊂design␈α⊂engineer␈α∂at␈α⊂SAIL␈α⊂for␈α∂ten          ␈↓ π∞␈↓↓␈↓ π>Programmer's Manual,␈↓, MIT Press, 1962.
␈↓ ↓N␈↓years,␈α∃and␈α∃had␈α∃several␈α∃years␈α⊗of␈α∃electronics
␈↓ ↓N␈↓experience␈αbefore␈αthat.␈α
 Martin␈αFrost␈αhas␈α
been    ␈↓ π∞␈↓[12]    David C. Smith, ␈↓αMLISP User's
␈↓ ↓N␈↓a systems programmer at SAIL for ␈↓βC␈↓ve years. ␈↓ π∞␈↓α␈↓ π>Manual␈↓, Stanford AI Memo AIM-84,
                                            ␈↓ π∞␈↓␈↓ π>January 1969.
␈↓ ↓N␈↓α␈↓ β5References 
                                            ␈↓ π∞␈↓[13]    John Reiser (ed.), ␈↓αSAIL␈↓, Stanford AI
␈↓ ↓N␈↓[1]    Tom McWilliams and Curt Widdoes,     ␈↓ π∞␈↓␈↓ π>Memo AIM-289, August 1976.
␈↓ ↓N␈↓␈↓ ↓}␈↓αThe S-1 Memory Interface␈↓, October 3,
␈↓ ↓N␈↓␈↓ ↓}1977.                                       ␈↓ π∞␈↓[14]    William Weiher and Steve Savitzky,
                                            ␈↓ π∞␈↓␈↓ π>␈↓αSon of Stopgap␈↓, SAILON-50.3, October
␈↓ ↓N␈↓[2]    John McCarthy, ␈↓αA Time Sharing        ␈↓ π∞␈↓␈↓ π>1970.
␈↓ ↓N␈↓α␈↓ ↓}Operator Program for our Projected IBM
␈↓ ↓N␈↓α␈↓ ↓}709␈↓, memo to P. M. Morse, MIT, January      ␈↓ π∞␈↓[15]    Arthur Samuel and Martin Frost, ␈↓αE
␈↓ ↓N␈↓␈↓ ↓}1, 1959.                                    ␈↓ π∞␈↓α␈↓ π>Text Editor␈↓, Program Note, December
                                            ␈↓ π∞␈↓␈↓ π>1977.
␈↓ ↓N␈↓[3]    John McCarthy, S. Boilen, E. Fredkin,
␈↓ ↓N␈↓␈↓ ↓}J.C.R. Licklider, ␈↓αA Time-sharing            ␈↓ π∞␈↓[16]    Phil Petit, ␈↓αRAID␈↓, SAILON-58.1,
␈↓ ↓N␈↓α␈↓ ↓}Debugging System for a Small                ␈↓ π∞␈↓␈↓ π>February 1970.
␈↓ ↓N␈↓α␈↓ ↓}Computer␈↓, ␈↓↓Proc. AFIP Conf.␈↓ (SJCC), Vol.
␈↓ ↓N␈↓␈↓ ↓}23, 1963.                                   ␈↓ π∞␈↓[17]    Larry Tesler, ␈↓αPUB, the Document
                                            ␈↓ π∞␈↓α␈↓ π>Compiler␈↓, SAILON-70, September 1970.
␈↓ ↓N␈↓[4]    John McCarthy, D. Brian, G. Feldman,
␈↓ ↓N␈↓␈↓ ↓}J. Allen, ␈↓αTHOR ␈↓␈↓βe␈↓␈↓α A Display Based            ␈↓ π∞␈↓[18]    John McCarthy and Les Earnest,
␈↓ ↓N␈↓α␈↓ ↓}Time-sharing System␈↓, ␈↓↓Proc. AFIPS Conf.␈↓      ␈↓ π∞␈↓␈↓ π>␈↓αDIALNET and the Home Terminal␈↓, ␈↓↓Proc.
␈↓ ↓N␈↓␈↓ ↓}(FJCC), Vol. 30, Thompson, Washington,      ␈↓ π∞␈↓↓␈↓ π>Computer Faire␈↓, San Francisco, 1977.
␈↓ ↓N␈↓␈↓ ↓}D.C., 1967.
␈↓ ↓N␈↓α␈↓ ε↑␈↓ ←8


␈↓ ↓N␈↓α␈↓ β*Appendix D                                  ␈↓ π∞␈↓      h. Hilding Elmquist ␈↓ 
Z3.0␈↓ 
} ␈↓ ,3,683
␈↓ ↓N␈↓α␈↓ βOBudget                                      ␈↓ π∞␈↓         Systems Programmer, 25%

                                            ␈↓ π∞␈↓      i. Student Res. Assist. ␈↓ 
Z7.5␈↓ 
} ␈↓ ,7,765
␈↓ ↓N␈↓␈↓ ↓lTwelve months beginning 1 January 1979      ␈↓ π∞␈↓         50% acad. yr., 100% sum.

␈↓ ↓N␈↓␈↓ ∧d␈↓αPerson␈↓ ¬>                                      ␈↓ π∞␈↓      j. Support Personnel:
␈↓ ↓N␈↓α␈↓ ∧ZMonths␈↓ ¬>
␈↓ ↓N␈↓αA. Salaries and Wages␈↓                       ␈↓ π∞␈↓         (1) Secretary (75%) ␈↓ 
Z9.0␈↓ 
} ␈↓ ,8,839

␈↓ ↓N␈↓   1. Senior Personnel:                     ␈↓ π∞␈↓         (2) Elect. Tech. (25%) ␈↓ 
Z3.0␈↓ 
} ␈↓ ,4,198
                                            ␈↓ π∞␈↓␈↓ _______
␈↓ ↓N␈↓      a. John McCarthy ␈↓ ¬~0.8␈↓ ¬> ␈↓ ¬l2,956            ␈↓ π∞␈↓      Total Salaries & Wages ␈↓ ∞159,781
␈↓ ↓N␈↓         Prof. of Computer Science
␈↓ ↓N␈↓         5% acad. yr., 10% summer           ␈↓ π∞␈↓␈↓αB. Sta␈↓␈↓β`␈↓␈↓α Bene␈↓␈↓βc␈↓␈↓αts␈↓ ␈↓ ≥32,276
                                            ␈↓ π∞␈↓     19.5% till 1 Sept.'79,
␈↓ ↓N␈↓      b. Forest Baskett ␈↓ ¬~3.5␈↓ ¬> ␈↓ ¬l9,152           ␈↓ π∞␈↓     21.6% thereafter
␈↓ ↓N␈↓         Assoc. Prof. of C.S. & E.E.
␈↓ ↓N␈↓         25% acad. yr., 40% sum.            ␈↓ π∞␈↓␈↓αC. Travel␈↓ (domestic) ␈↓ ,7,500

␈↓ ↓N␈↓      c. Lester Earnest ␈↓ ¬~1.8␈↓ ¬> ␈↓ ¬l6,010           ␈↓ π∞␈↓␈↓αD. Other direct costs ␈↓ ␈↓ ≥22,700
␈↓ ↓N␈↓         Senior Research Associate          ␈↓ π∞␈↓     (e.g. telephone, publications,
␈↓ ↓N␈↓         15%                                ␈↓ π∞␈↓     o␈↓α␈↓β@␈↓α␈↓ice supplies, copying,
                                            ␈↓ π∞␈↓     postage, computer repair services)
␈↓ ↓N␈↓   2. Other Personnel (full time except
␈↓ ↓N␈↓      where speci␈↓α␈↓βC␈↓α␈↓ed otherwise):            ␈↓ π∞␈↓␈↓αE. Indirect Costs␈↓ ␈↓ ∞128,909
                                            ␈↓ π∞␈↓     (58% of A thru D)
␈↓ ↓N␈↓      a. Je␈↓α␈↓β@␈↓α␈↓ Rubin ␈↓ ¬12.0␈↓ ¬> ␈↓ ¬]29,143
␈↓ ↓N␈↓         Computer Systems Specialist        ␈↓ π∞␈↓␈↓αF. Permanent Equipment␈↓ ␈↓ ,7,200
                                            ␈↓ π∞␈↓     3 Datamedia display terminals
␈↓ ↓N␈↓      b. John Hennessey ␈↓ ¬~3.0␈↓ ¬> ␈↓ ¬l5,966
␈↓ ↓N␈↓         Asst. Prof. of E.E.                ␈↓ π∞␈↓␈↓ _______
␈↓ ↓N␈↓         20% acad. yr., 40% sum.            ␈↓ π∞␈↓␈↓αG. Total Costs ␈↓ ∩358,366

␈↓ ↓N␈↓      c. Arthur Samuel ␈↓ ¬~6.0␈↓ ¬> ␈↓ ¬]18,414
␈↓ ↓N␈↓         Adjunct Prof. of C.S.
␈↓ ↓N␈↓         50%

␈↓ ↓N␈↓      d. ␈↓α␈↓βE␈↓α␈↓␈↓α␈↓βE␈↓α␈↓␈↓α␈↓βE␈↓α␈↓␈↓α␈↓βE␈↓α␈↓␈↓α␈↓βE␈↓α␈↓ ␈↓ ¬12.0␈↓ ¬> ␈↓ ¬]22,342
␈↓ ↓N␈↓         Systems Programmer

␈↓ ↓N␈↓      e. Martin Frost ␈↓ ¬~4.0␈↓ ¬> ␈↓ ¬l6,547
␈↓ ↓N␈↓         Systems Programmer

␈↓ ↓N␈↓      f. Mark Lebrun ␈↓ ¬12.0␈↓ ¬> ␈↓ ¬]18,414
␈↓ ↓N␈↓         Systems Programmer

␈↓ ↓N␈↓      g. Armando Rodriguez ␈↓ ¬12.0␈↓ ¬> ␈↓ ¬]16,352
␈↓ ↓N␈↓         Systems Programmer
␈↓ ↓N␈↓α␈↓ b1


␈↓ ↓N␈↓ε            AN EXTENSION TO THE PROGRAMMING LANGUAGE PASCAL,
␈↓ ↓N␈↓ε                     TO SUPPORT SYSTEMS PROGRAMMING



␈↓ ↓N␈↓ε                             John Hennessy
␈↓ ↓N␈↓ε                             Forest Baskett

␈↓ ↓N␈↓ε                           November 15, 1978






␈↓ ↓N␈↓ε1.0 INTRODUCTION
␈↓ ↓N␈↓ε        This report  defines  an  upward  compatible  extension  of  the
␈↓ ↓N␈↓εprogramming  language  Pascal. This extension is designed to support the
␈↓ ↓N␈↓εconstruction of large systems programs. A major attempt has been made to
␈↓ ↓N␈↓εkeep  the goals of Pascal intact; in particular attention is directed at
␈↓ ↓N␈↓εsimplicity, efficient runtime implementation and efficient  compilation,
␈↓ ↓N␈↓εlanguage security, and compile-time type checking.

␈↓ ↓N␈↓ε1.1 Report
␈↓ ↓N␈↓ε        This report consists of four major sections. This first section,
␈↓ ↓N␈↓εintroduces  the  language and two general extensions. The second section
␈↓ ↓N␈↓εdefines a number of major language features and gives examples. The last
␈↓ ↓N␈↓εtwo  sections  are appendices: the first discusses a number of the major
␈↓ ↓N␈↓εdesign decisions behind the features of section2,  the  second  appendix
␈↓ ↓N␈↓εpresents  some additional possible extensions which are interesting, but
␈↓ ↓N␈↓εare either still vague or do not seem necessary.

␈↓ ↓N␈↓ε1.2 Defining Notation
␈↓ ↓N␈↓ε        This  report  uses  the  BNF notation defined in the Pascal user
␈↓ ↓N␈↓εManual. The existing BNF is not repeated but merely referred to (by  the
␈↓ ↓N␈↓εuse of nonterminal symbols defined by that grammar).
␈↓ ↓N␈↓ε        The  semantics  are  defined  informally;  a  formal   axiomatic
␈↓ ↓N␈↓εdefinition for the new features may be available later.

␈↓ ↓N␈↓ε1.3 Restrictions
␈↓ ↓N␈↓ε        This extension  is  completely  upward  compatible  with  the
␈↓ ↓N␈↓εPascal  standard,  except for one point. This extension requires that
␈↓ ↓N␈↓εprocedures which are parameters be fully typed, by defining the types
␈↓ ↓N␈↓εof  all  the  parameters  and  the  resultant  type  in the case of a
␈↓ ↓N␈↓εfunction. Thus the grammar for  a  parameter  which  is  a  procedure
␈↓ ↓N␈↓εbecomes:

␈↓ ↓N␈↓ε<formal parameter section> ::= <parameter group> 
␈↓ ↓N␈↓ε                             | var <parameter group>
␈↓ ↓N␈↓ε                             | <function heading> | <procedure heading>
␈↓ ↓N␈↓α␈↓ `2


␈↓ ↓N␈↓ε1.4 General Extensions
␈↓ ↓N␈↓ε        Two minor but general extensions to  the  language  are  defined
␈↓ ↓N␈↓εhere.   The  first  is  the  relaxation  of the order of declaration for
␈↓ ↓N␈↓εconstants,  types,  variables,   procedures   and   functions.     These
␈↓ ↓N␈↓εdeclaration sections are allowed to occur in any order and may occur any
␈↓ ↓N␈↓εnumber of times .  It is required that an identifier be declared  before
␈↓ ↓N␈↓εit  is  used.   Pointer  types are excluded from this rule. To eliminate
␈↓ ↓N␈↓εambiguity, the following rule is introduced:
␈↓ ↓N␈↓ε     If  a declaration refers to an identifier x, that identifier may
␈↓ ↓N␈↓ε     not be declared later in the same scope, if it is declared in  a
␈↓ ↓N␈↓ε     surrounding scope.

␈↓ ↓N␈↓εThe new syntax for the declaration section becomes:
␈↓ ↓N␈↓ε<block> ::= <label declaration part> <declarations> <statement part>
␈↓ ↓N␈↓ε<declarations> ::= empty | <declaration> <declarations>
␈↓ ↓N␈↓ε<declaration> ::= <constant definition part> | <type definition part>
␈↓ ↓N␈↓ε                | <variable declaration part>
␈↓ ↓N␈↓ε                | <procedure and function declaration part>

␈↓ ↓N␈↓ε        The  second  extension  is  to  allow  the  utilization of an
␈↓ ↓N␈↓εinclude command.   This command with the syntax  include  <filename>,
␈↓ ↓N␈↓εwill  cause the text in the file <filename> to be inserted in line in
␈↓ ↓N␈↓εthe program.  The  command  may  appear  only  where  a  <block>,  or
␈↓ ↓N␈↓ε<declarations>  could  appear.   Thus  this  construct can be used to
␈↓ ↓N␈↓εinclude sets of declarations and/or procedures or functions.


␈↓ ↓N␈↓ε2.0 SPECIFIC EXTENDED LANGUAGE FEATURES

␈↓ ↓N␈↓εThis  section  defines  a  number  of specific language extensions to
␈↓ ↓N␈↓εPascal.

␈↓ ↓N␈↓ε2.1 Type Constructors

␈↓ ↓N␈↓ε<type constructor> ::= <type identifier> (<type specifier> )
␈↓ ↓N␈↓ε<type identifier> ::= identifier
␈↓ ↓N␈↓ε<type specifier> ::= <expression> 
␈↓ ↓N␈↓ε                   |<type specifier> {, <type specifier>}
␈↓ ↓N␈↓ε                   | ( <type specifier> )
␈↓ ↓N␈↓ε                   | <type constructor>

␈↓ ↓N␈↓ε        Consider  a type constructor of the form T ( <type specifier>
␈↓ ↓N␈↓ε). The type name must not be a parameterized type. The  form  of  the
␈↓ ↓N␈↓ε<type specifier> depends on the type name, T. The type T dictates the
␈↓ ↓N␈↓εform of the type specifier and the result of the type constructor, by
␈↓ ↓N␈↓εthe following rules:
␈↓ ↓N␈↓ε  1. Simple type or set type, then the  type  specifier  must  be  an
␈↓ ↓N␈↓ε     expression  whose  value  is  implicitly coerceable to the type.
␈↓ ↓N␈↓ε     The result is a value of type T equal to the value of  the  type
␈↓ ↓N␈↓ε     specifier expression.
␈↓ ↓N␈↓ε  2. Array type, then the type constructor must be a list of  values,
␈↓ ↓N␈↓ε     whose types match the component type of the array. The result is
␈↓ ↓N␈↓ε     a value of the array type  T,  with  the  components  being  the
␈↓ ↓N␈↓ε     values  in  the type specifier. The matching of array components
␈↓ ↓N␈↓ε     to values is  by  increasing  indices  matched  with  increasing
␈↓ ↓N␈↓ε     positions in the list of values.
␈↓ ↓N␈↓α␈↓ `3


␈↓ ↓N␈↓ε 3.  Record type, then the type specifier must be a list of values which
␈↓ ↓N␈↓ε     match the fields of the record in order of  declaration  (including
␈↓ ↓N␈↓ε     tag  field).   The  result  is  a  value of type T, with the record
␈↓ ↓N␈↓ε     fields equal to the corresponding values from  the  type  specifier
␈↓ ↓N␈↓ε     list.

␈↓ ↓N␈↓ε        Type  constructors  may  appear  anywhere  a  variable  of   the
␈↓ ↓N␈↓εconstructed  type could appear, except that they may not be assigned to.
␈↓ ↓N␈↓εFurthermore, if all the expressions in a type specifier are compile-time
␈↓ ↓N␈↓εconstants  (see  next  section)  then  the result is a constant, and may
␈↓ ↓N␈↓εappear anywhere a constant might appear.
␈↓ ↓N␈↓ε        In  the  type constructor for a string or a packed array of char
␈↓ ↓N␈↓εthe abbreviation 'string of characters', may  be  used  for  a  list  of
␈↓ ↓N␈↓εcharacter  constants;  the number of elements in the list must match the
␈↓ ↓N␈↓εlength of the string of characters.

␈↓ ↓N␈↓ε2.1.1 Examples
␈↓ ↓N␈↓εtype    T = array [1..3] of integer;
␈↓ ↓N␈↓ε        R = record
␈↓ ↓N␈↓ε                field: integer;
␈↓ ↓N␈↓ε                field2: T;
␈↓ ↓N␈↓ε        end;

␈↓ ↓N␈↓ε        S = set of 1..20;

␈↓ ↓N␈↓εconst   OnetoThree = T (1,2,3);
␈↓ ↓N␈↓εvar     x:T;
␈↓ ↓N␈↓ε        i,j: integer;
␈↓ ↓N␈↓ε        sset: S;
␈↓ ↓N␈↓ε        rrecord: R;
␈↓ ↓N␈↓εtype    Matrix = array [1..2,1..2] of real;
␈↓ ↓N␈↓εconst   DiagMatrix = Matrix ((1,0),(0,1));

␈↓ ↓N␈↓εbegin
␈↓ ↓N␈↓ε        i := integer (4*5);
␈↓ ↓N␈↓ε        sset := S([1,5..10,17]);
␈↓ ↓N␈↓ε        rrecord := R(i,T(i,10,25));
␈↓ ↓N␈↓ε        j := i + 45;
␈↓ ↓N␈↓ε        x := T (4,5,i*j);
␈↓ ↓N␈↓εend.

␈↓ ↓N␈↓ε2.2 Extended Constants

␈↓ ↓N␈↓ε<constant definition> ::= <identifier> = <expression>

␈↓ ↓N␈↓ε        The  concept  of a constant is extended to allow a broader class
␈↓ ↓N␈↓εof defining mechanisms. The first extension is to allow constants to  be
␈↓ ↓N␈↓εdefined  by  any  compile-time  computable  expression.  A  compile-time
␈↓ ↓N␈↓εcomputable expression is defined to be an expression consisting  of  any
␈↓ ↓N␈↓εof   the   following:   manifest   constants,  defined  constants,  type
␈↓ ↓N␈↓εconstructors, and the standard Pascal operators.   The  effect  of  this
␈↓ ↓N␈↓εextension  is  two  fold: constants may be compile-time expressions, and
␈↓ ↓N␈↓εconstants may be defined of arbitrary types, including structured types.
␈↓ ↓N␈↓α␈↓ ]4


␈↓ ↓N␈↓ε2.3 Modules

␈↓ ↓N␈↓ε<module> ::= module <module identifier> <file list>; <block> .
␈↓ ↓N␈↓ε<file list> ::= <empty> 
␈↓ ↓N␈↓ε              | ( <file identifier> {, <file identifier>} )

␈↓ ↓N␈↓ε        The module  facility  provides  the  ability  to  encapsulate
␈↓ ↓N␈↓εprocedures, functions, data and types, as well as supporting separate
␈↓ ↓N␈↓εcompilation. Modules may be separately compiled, and intermodule type
␈↓ ↓N␈↓εchecking  will  be  done  as  part  of the linking process. Unless an
␈↓ ↓N␈↓εidentifier is exported from a module, it is local to that module  and
␈↓ ↓N␈↓εcan  not  be  used  from  other  modules.  Likewise  all  identifiers
␈↓ ↓N␈↓εreferenced in a module must be either local or imported from  another
␈↓ ↓N␈↓εmodule.

␈↓ ↓N␈↓ε2.2.1 Importing and exporting from modules

␈↓ ↓N␈↓ε<declarations> ::= empty | import <declarations> end; <declarations>
␈↓ ↓N␈↓ε                 | export <declarations> end; <declarations>
␈↓ ↓N␈↓ε                 | <declaration> <declarations>
␈↓ ↓N␈↓ε<procedure declaration> ::= <procedure heading> external
␈↓ ↓N␈↓ε                          | <procedure heading> <block>
␈↓ ↓N␈↓ε                          | <procedure heading> forward
␈↓ ↓N␈↓ε<function declaration> ::= <function heading> external
␈↓ ↓N␈↓ε                         | <function heading> <block>
␈↓ ↓N␈↓ε                         | <function heading> forward

␈↓ ↓N␈↓ε        Importing allows the use of variables,  types,  procedures,  and
␈↓ ↓N␈↓εfunctions  which are defined by other modules. Exporting allows a module
␈↓ ↓N␈↓εto make procedures, functions, variables and types  available  to  other
␈↓ ↓N␈↓εmodules. All exported identifiers are treated as globals to all modules.
␈↓ ↓N␈↓εIn order to reference an object declared by another module, it  must  be
␈↓ ↓N␈↓εexported  by  the declaring module and imported by the accessing module.
␈↓ ↓N␈↓εSince strong type checking is used, it is highly recommended that  types
␈↓ ↓N␈↓εbe  exported and imported whenever a variable or procedure requires type
␈↓ ↓N␈↓εdefinitions. Import and export sections may not be nested.

␈↓ ↓N␈↓ε2.2.2 An example - defining a stack module

␈↓ ↓N␈↓εmodule Stack;
␈↓ ↓N␈↓ε(* defines an integer stack of size <= 100 *)

␈↓ ↓N␈↓εexport
␈↓ ↓N␈↓εtype    StackBounds = 0..100;
␈↓ ↓N␈↓ε        Stk = record
␈↓ ↓N␈↓ε                sp: StackBounds := StackBounds(0);
␈↓ ↓N␈↓ε                intstack: array [StackBounds] of integer;
␈↓ ↓N␈↓ε        end;

␈↓ ↓N␈↓ε        procedure push (var s: stk; item: integer); forward;

␈↓ ↓N␈↓ε        function pop (var s: stk): integer; forward;

␈↓ ↓N␈↓ε        function empty (s: stk): boolean;
␈↓ ↓N␈↓ε        begin
␈↓ ↓N␈↓ε                if s.sp = 0 then empty := true else empty := false;
␈↓ ↓N␈↓ε        end;
␈↓ ↓N␈↓εend;
␈↓ ↓N␈↓α␈↓ ←5


␈↓ ↓N␈↓εprocedure push (var s:stk; item: integer);
␈↓ ↓N␈↓εbegin
␈↓ ↓N␈↓ε        with s do if sp = 100 then ERROR
␈↓ ↓N␈↓ε        else begin
␈↓ ↓N␈↓ε                sp := succ (sp);
␈↓ ↓N␈↓ε                intstack [sp] := item
␈↓ ↓N␈↓ε        end
␈↓ ↓N␈↓εend;    (* push *)

␈↓ ↓N␈↓εfunction pop (var s: stk): integer;
␈↓ ↓N␈↓εbegin
␈↓ ↓N␈↓ε        if empty (s) then ERROR
␈↓ ↓N␈↓ε        else with s do begin
␈↓ ↓N␈↓ε                pop := intstack[sp];
␈↓ ↓N␈↓ε                sp := pred(sp);
␈↓ ↓N␈↓ε        end;
␈↓ ↓N␈↓εend;    (* Pop *)

␈↓ ↓N␈↓εend (* Stack *);


␈↓ ↓N␈↓εmodule UseStack;

␈↓ ↓N␈↓εimport 
␈↓ ↓N␈↓ε        type    StackBounds = 1..100;
␈↓ ↓N␈↓ε                stk: record
␈↓ ↓N␈↓ε                        sp: StackBounds := StackBounds(0);
␈↓ ↓N␈↓ε                        intstack: array [StackBounds] of integer
␈↓ ↓N␈↓ε                end;

␈↓ ↓N␈↓ε        procedure push (s: stk; i: integer); external;
␈↓ ↓N␈↓ε        function pop (s: stk): integer; external;
␈↓ ↓N␈↓ε        function empty (s: stk): boolean; external;
␈↓ ↓N␈↓εend;


␈↓ ↓N␈↓εvar s: stk;

␈↓ ↓N␈↓ε    i: integer;

␈↓ ↓N␈↓ε .....
␈↓ ↓N␈↓εpush (s,i);


␈↓ ↓N␈↓εend (* UseStack *);

␈↓ ↓N␈↓ε(Note  that  this  function  is  really  more  suited  towards  a   data
␈↓ ↓N␈↓εabstraction  facility. The module facility is designed to support larger
␈↓ ↓N␈↓εfunctional units. The above example is only for illustration.)
␈↓ ↓N␈↓α␈↓ `6


␈↓ ↓N␈↓ε2.4 Variable Initialization

␈↓ ↓N␈↓ε<variable declaration> ::= <identifier> {,<identifier>} : <type> variable init>
␈↓ ↓N␈↓ε<variable init> ::= <empty> | := <type constructor>
␈↓ ↓N␈↓ε<record section> ::= <field identifier> {,<field identifier>} : <type> <variable init>
␈↓ ↓N␈↓ε                     | <empty>
␈↓ ↓N␈↓ε 
␈↓ ↓N␈↓ε        Variable initialization is only allowed to variables   and fields of records at  the
␈↓ ↓N␈↓εglobal level of a module or a program. The type constructor must be a
␈↓ ↓N␈↓εconstant. All variables in the identifier list  or field list are initialized to the
␈↓ ↓N␈↓εsame value.

␈↓ ↓N␈↓ε2.5 Explicit Type Coercion Functions
␈↓ ↓N␈↓ε        Explicit type coercion functions which will convert the  type
␈↓ ↓N␈↓εof  an  expression from one type to another type whose representation
␈↓ ↓N␈↓εlength is the same are provided. These coercion  functions  take  the
␈↓ ↓N␈↓εform  of  a  predefined  set  of functions; their implementation is a
␈↓ ↓N␈↓εcompile-time operation of altering  the  type  (no  value  change  is
␈↓ ↓N␈↓εdone).

␈↓ ↓N␈↓ε2.6 Parametric Types
␈↓ ↓N␈↓ε 
␈↓ ↓N␈↓ε<type definition> ::= <identifier> = <type> 
␈↓ ↓N␈↓ε                    | <parameterized type>
␈↓ ↓N␈↓ε<parameterized type> ::= <identifier> <type parameter list> = <compound type>
␈↓ ↓N␈↓ε<compound type> ::= <array type> | <record type>
␈↓ ↓N␈↓ε<type parameter list> ::= ( <type parameter> {,<type parameter>} )
␈↓ ↓N␈↓ε<type parameter> ::= <identifier> {,<identifier>} : <simple type>

␈↓ ↓N␈↓ε 
␈↓ ↓N␈↓ε        A   parameterized  type  is  a  type  definition  where  certain
␈↓ ↓N␈↓εidentifiers, which would  normally  be  constants,  are  allowed  to  be
␈↓ ↓N␈↓εunspecified  parameters.  These  parameters  can only be used to specify
␈↓ ↓N␈↓εparameters in a component of the <compound type>  or  to  specify  array
␈↓ ↓N␈↓εbounds. A parameterized array type is an array type with the bounds left
␈↓ ↓N␈↓εspecified as parameters.  The identifiers which are type parameters  are
␈↓ ↓N␈↓εlocal  to  the  type  definition.  Identifiers  within  the <array type>
␈↓ ↓N␈↓εspecification which are also in the the type parameter list are bound to
␈↓ ↓N␈↓εthose  type  parameters.  The  type parameters can only appear where the
␈↓ ↓N␈↓εarray bounds  are  being  specified  (though  they  may  appear  in  the
␈↓ ↓N␈↓εspecification of the bounds of a component type).   Also the bounds must
␈↓ ↓N␈↓εbe specified as subranges, if the parameterized types are used.
␈↓ ↓N␈↓ε        Parameterized types allow the  implementation  of  procedures
␈↓ ↓N␈↓εwhich  may  accept  a variety of different array sizes. Thus a formal
␈↓ ↓N␈↓εarray parameter can  be  specified  to  be  a  parametric  type.  All
␈↓ ↓N␈↓εdeclarations  of  variables and constants must supply constant values
␈↓ ↓N␈↓εfor the actual parameters.
␈↓ ↓N␈↓ε        Since  a  parameterized  array could be a component of a record,
␈↓ ↓N␈↓εrecord types  are  also  allowed  to  have  parameters.  However,  these
␈↓ ↓N␈↓εparameters  can  only  be used to define the bounds of arrays within the
␈↓ ↓N␈↓εrecord.
␈↓ ↓N␈↓ε        Two  predefined  functions upper and lower are provided. Both
␈↓ ↓N␈↓εfunctions take a single parameter of any array type, and  return  the
␈↓ ↓N␈↓εlower, or upper bound of that array.
␈↓ ↓N␈↓α␈↓ `7


␈↓ ↓N␈↓ε2.6.1 Example
␈↓ ↓N␈↓ε        In this example the stack module is  parameterized  to  allow
␈↓ ↓N␈↓εvariable size stacks.

␈↓ ↓N␈↓εmodule Stack;

␈↓ ↓N␈↓εexport 
␈↓ ↓N␈↓ε        type stackbounds= 1..100;
␈↓ ↓N␈↓ε        stk (size: Stackbounds) = record
␈↓ ↓N␈↓ε                sp: stackbounds := stackbounds(0);
␈↓ ↓N␈↓ε                intstack: array [1..size] of integer;
␈↓ ↓N␈↓ε        end;
␈↓ ↓N␈↓εend;

␈↓ ↓N␈↓εprocedure push (var s: stk; item: integer);
␈↓ ↓N␈↓εbegin
␈↓ ↓N␈↓ε        with s do if s.sp=upper(s.intstack) then ERROR
␈↓ ↓N␈↓ε        ...
␈↓ ↓N␈↓ε        ...
␈↓ ↓N␈↓εend; (* STACK *)



␈↓ ↓N␈↓εvar     s: stk(20);
␈↓ ↓N␈↓ε        i: integer;
␈↓ ↓N␈↓ε        ...
␈↓ ↓N␈↓ε        ...

␈↓ ↓N␈↓ε        push (s,i);

␈↓ ↓N␈↓ε2.7 Strings
␈↓ ↓N␈↓ε        A string facility which provides varying length strings  with
␈↓ ↓N␈↓εa maximum size limit on each string is included. The type string is a
␈↓ ↓N␈↓εparametric type where the parameter specifies the upper bound on that
␈↓ ↓N␈↓εstring. The logical view on a string is defined by:
␈↓ ↓N␈↓ε 
␈↓ ↓N␈↓εtype string (n) = record
␈↓ ↓N␈↓ε                        length : 0..maxint;
␈↓ ↓N␈↓ε                        text : packed array [1..n] of char;
␈↓ ↓N␈↓ε                 end
␈↓ ↓N␈↓εNote  that the string package is not really a language extension because
␈↓ ↓N␈↓εit consists of only a predefined type and a set of predefined procedures
␈↓ ↓N␈↓εoperating on that type.
␈↓ ↓N␈↓ε        Pascal string constants of the form 'characters' are  treated
␈↓ ↓N␈↓εas  string  constants where the actual parameter is the length of the
␈↓ ↓N␈↓εstring.  Thus  the  constant  'ABC',  has  type  string(3),  and   is
␈↓ ↓N␈↓εconsidered an abbreviation for:
␈↓ ↓N␈↓εtype string3 = string(3);

␈↓ ↓N␈↓ε        string3(3,'ABC')
␈↓ ↓N␈↓ε 
␈↓ ↓N␈↓α␈↓ ←8


␈↓ ↓N␈↓ε        The type string is  supported  by  a  variety  of  predefined
␈↓ ↓N␈↓εprocedures for manipulating strings. These are briefly defined below:

␈↓ ↓N␈↓ε 
␈↓ ↓N␈↓εprocedure ASSIGN (source: string; var dest:string);
␈↓ ↓N␈↓ε        dest <= source

␈↓ ↓N␈↓εfunction LENGTH (source: string): 0..maxint;
␈↓ ↓N␈↓ε        LENGTH <= source.length

␈↓ ↓N␈↓εfunction POS (string1, string2: string): 0..maxint;
␈↓ ↓N␈↓ε        POS <= starting position of string1 pattern in string2, else 0

␈↓ ↓N␈↓εprocedure SUBSTR (source: string; var dest: string; sourcepos,
␈↓ ↓N␈↓ε   destpos: 1..maxint; leng:0..maxint);

␈↓ ↓N␈↓ε        dest.text [destpos..destpos+leng-1] <= source[sourcepos..sourcepos
␈↓ ↓N␈↓ε           +leng-1];
␈↓ ↓N␈↓ε        dest.leng <= max (dest.length,destpos+length-1);

␈↓ ↓N␈↓εprocedure CONCAT (source: string; var dest: string);
␈↓ ↓N␈↓ε        dest.text [dest.length+1..dest.length+1+source.length] <= source.text
␈↓ ↓N␈↓ε        dest.length <= dest.length + source.length;

␈↓ ↓N␈↓εfunction GETCHAR (source: string; sourcepos:1..maxint): char;
␈↓ ↓N␈↓ε        GETCHAR <= source.text[sourcepos];

␈↓ ↓N␈↓εprocedure PUTCHAR (source: char; var dest: string; destpos: 1..maxint);
␈↓ ↓N␈↓ε        dest[destpos] := source;

␈↓ ↓N␈↓εThe following string comparasion functions are supplied:
␈↓ ↓N␈↓ε        STREQ,STRNE,STRLT,STRGT,STRGE,STRLE.
␈↓ ↓N␈↓εAll  take  two  strings  as  operands and return true if the relation
␈↓ ↓N␈↓εholds.
␈↓ ↓N␈↓ε 
␈↓ ↓N␈↓ε        The  standard procedures READ and WRITE are adapted to handle
␈↓ ↓N␈↓εstrings.

␈↓ ↓N␈↓ε2.8 Loop-Exit Construct
␈↓ ↓N␈↓ε 
␈↓ ↓N␈↓ε<loop statement> ::=  loop <statement> {; <statement>} end
␈↓ ↓N␈↓ε<exit statement> ::= exit
␈↓ ↓N␈↓ε 
␈↓ ↓N␈↓ε        The loop construct creates an potentially infinite loop, with no
␈↓ ↓N␈↓εexplicit  termination  condition  (unlike  the while or for statements).
␈↓ ↓N␈↓εWithin a loop statement one or  more  exit  statements  can  occur.  The
␈↓ ↓N␈↓εstatement  exit  may  only  occur  within  the  static nesting of a loop
␈↓ ↓N␈↓εstatement.  The semantics of the exit statement are to stop execution of
␈↓ ↓N␈↓εthe  immediately  surrounding  loop statement and begin execution at the
␈↓ ↓N␈↓εstatement following the end of the loop.
␈↓ ↓N␈↓α␈↓ `9


␈↓ ↓N␈↓ε2.9 Packed Structures
␈↓ ↓N␈↓ε        Provision  is  made  for  specifying  two  types  of  storage
␈↓ ↓N␈↓εpacking.  If no packing is specified storage is allocated to optimize
␈↓ ↓N␈↓εaccess.  Packing  is  only   effective   on   arrays   and   records.
␈↓ ↓N␈↓εSpecification  of  the  attribute packed will cause a decrease in the
␈↓ ↓N␈↓εuse  of  storage.  The  compiler  will  allocate  packed   items   by
␈↓ ↓N␈↓εaddressable  units.  Thus  each item in a packed array or record will
␈↓ ↓N␈↓εoccupy the next largest addressable unit (byte, halfword, word), that
␈↓ ↓N␈↓εwill accomodate its value range.
␈↓ ↓N␈↓ε        The attribute bit packed can only be applied to record types.
␈↓ ↓N␈↓εIt  will cause allocation of the fields of a record to be bit packed.
␈↓ ↓N␈↓εThus the number of bits occupied by  a  field  will  be  the  minimum
␈↓ ↓N␈↓εnumber necessary to hold the range values of that field.
␈↓ ↓N␈↓ε2.10 Storage Management
␈↓ ↓N␈↓ε        The implementation will provide a standard procedure DISPOSE,
␈↓ ↓N␈↓εwhich takes a single parameter of any pointer type. The result of the
␈↓ ↓N␈↓εprocedure is two-fold: the storage associated with the ptr  is  freed
␈↓ ↓N␈↓ε(and  made  eligible for later allocation), and the pointer is set to
␈↓ ↓N␈↓εNIL.

␈↓ ↓N␈↓ε2.11 Type Coercion
␈↓ ↓N␈↓ε        Because the need to occasionally  violate  the  type  system  is
␈↓ ↓N␈↓εforseeable,  a  method  for  doing  this  in an explicit manner has been
␈↓ ↓N␈↓εincluded. A set of prdefined functions will provide coercion between any
␈↓ ↓N␈↓εtwo  length  compatable  types.  Note  that  the  coercion functions are
␈↓ ↓N␈↓εessentially a compile-time vehicle for altering a type.  They  will  not
␈↓ ↓N␈↓εrequire any runtime overhead.